package 动态规划.背包And分组And切割问题系列;

public class  leetcode6244完美分割方案 {
	
	public static boolean [] flag = {false, false, true, true, false, true, false, true, false, false};
    int MOD = 1000000007;
    
	public static final int cons = (int) (1e9 + 7);
	
	public static void main(String []args) {
//		String s = "7753639519183359148598823162755335682921461647796985255166979917649578972791819356618496239687361868933775339936875893219782348459522657159781118588765368954599285197845124455559747963186111993765269";
//		int k = 24;
//		int minLength = 2;
		String s = "23542185131";
		int k = 3;
		int minLength = 2;
//		System.out.println(solution(s,k,minLength));
//		System.out.println(dp(s,k,minLength));
//		System.out.println(dpFinal(s,k,minLength));
		System.out.println(dpFinally(s,k,minLength));
		
	}
	
	/**
	 * 这个 暴力 递归 ， 真的有点难写的
	 */
	public static int solution(String s,int k,int minLength) {
		if(s.length() < k * minLength)
			return 0;
		return recursion(0,k,minLength,s.toCharArray(),s.length());
	}
	
	public static int recursion(int index,int k,int minLength,char [] str,int len) {
		if( index == len)
			return k == 0 ? 1 : 0;
		if(!judge(str[index]))
			return 0;
		
		int ans = 0;
		for(int scale = minLength;index + scale <= len ;scale++) {
			if(!judge(str[index + scale - 1]))
			ans += recursion(index + scale,k - 1,minLength,str,len);
		}
		
		return ans;
	}
	
	
	
	public static boolean judge(char ch) {
		if(ch == '2' ||  ch == '3' || ch == '5' || ch == '7')
			return true;
		return false;
	}
	
	/**
	 * 改成dp
	 * 还是超时
	 * 优化 一下 常数时间
	 *可以ac
	 */
	
	public static int dp(String s,int k,int minLength) {
		char [] str = s.toCharArray();
		int len = str.length;
		int dp [][] = new int [len + 1][k + 1];
		dp[len][0] = 1;
		for(int index = len - 1;index >= 0; index--) {
			if(!judge(str[index]))
				continue;
			for(int x = 1;x <= k ; x++) {
				int ans = 0;
				for(int scale = minLength;index + scale <= len; scale ++) {
					if(!judge(str[index + scale - 1]))
						ans += dp[index + scale][x - 1] ;
//						dp[index][x] = dp[index][x] % cons;
						ans = ans % cons;
				}
				dp[index][x] = ans % cons;
			}
		}
		for(int arr[] : dp) {
			for(int num : arr)
				System.out.print(num + "  ");
			System.out.println();
		}
		return dp[0][k];
	}
	
	/**
	 * 进行 斜率的优化
	 */
	public static int dpFinal(String s,int k,int minLength) {
		int len = s.length();
		int dp[][] = new int [len + 1][k + 1];
		char str[] = s.toCharArray();
		dp[len][0] = 1;
		for(int index = len - 1 ;index >= 0;index --) {
//			if(!flag[str[index] - '0'])
//				continue;
			for(int x = 1;x <= k;x ++){
				int ans = 0;
				if(index + minLength <= len ) {
//					if(!flag[str[index + minLength - 1] - '0']) {
//						ans = dp[index + minLength][x] + dp[index + minLength][x - 1];
//						ans += index + minLength + 1 <= len ? dp[index + minLength + 1][x - 1] : 0;
//					}
					ans = dp[index + minLength][x];
					if(!flag[str[index + minLength - 1] - '0']) {
						ans += dp[index + minLength][x - 1];
					}
					if(index + minLength + 1 <= len && !flag[str[index + minLength] - '0'])
						ans += dp[index + minLength + 1][x - 1];
				}
			dp[index][x] = ans;
			}
		}
		for(int arr[] : dp) {
			for(int num : arr)
				System.out.print(num + "  ");
			System.out.println();
		}
		return dp[0][k];
	}
	
	/**
	 * 通过上面的  测试， 直接使用斜率优化 ，成功不了！
	 * 但是 使用下面的方法 就 ，成功了 ，时间复杂度 O（N ^ k）
	 * 还有一个奇怪的现象, 就是:
	 * ① : preX += dp[index + minLength][x - 1] % cons;
	 * 上面 这样写,就会出现   int  溢出
	 * 但是 按照下面那样写, 就不会
	 *②:  preX = (preX + dp[index + minLength][x - 1]) % cons;
	 * 
	 * 其实 理由很简单!
	 * ①这种写法的话 只会 对 dp[index + minLength][x - 1] 取模
	 * 而 ②这种写法的话 , 是对 整体  (preX + dp[index + minLength][x - 1]) 取模
	 * 当然 不会溢出的 ,要注意 一些代码 细节  coding 的问题!  
	 */
	public static int dpFinally(String s,int k,int minLength) {
		int len = s.length();
		int dp[][] = new int [len + 1][k + 1];
		char str[] = s.toCharArray();
		dp[len][0] = 1;
		for(int x = 1;x <= k;x++) {
			int preX = 0;
			for(int index  = len -1; index >= 0;index --) {
				if(index + minLength > len)
					continue;
				if(!flag[str[index + minLength - 1] - '0'])
					preX =(preX + dp[index + minLength][x - 1]) % cons;
				if(!flag[str[index] - '0'])
						continue;
				dp[index][x] = preX;
			}
		}
		return dp[0][k];
	}
	
	
	
	
	
	

	    //boolean[] flag = new boolean[]{false, false, true, true, false, true, false, true, false, false};
/**
 * 
 */
	    public int beautifulPartitions(String s, int k, int minLength) {

	        char[] cs = s.toCharArray();
	        int N = cs.length; 
	        long[][] dp = new long[N + 1][k + 1];
	        if (!flag[cs[0] - '0'] || flag[cs[N - 1] - '0']) {
	            return 0;
	        }
	        dp[0][0] = 1;
	        for (int i = 1; i <= N; i++) {
	            for (int j = 1; j <= k; j++) {
	                long cur = 0;
	                if (i >= minLength && !flag[cs[i - 1] - '0']) {
	                    for (int l = i - minLength + 1; l >= 1; l--) {
	                        if (flag[cs[l - 1] - '0']) {
	                            cur += dp[l - 1][j - 1];
	                        }
	                    }
	                }
	                cur %= MOD;
	                dp[i][j] = cur;
	            }
	        }
	        return (int) dp[N][k];
	    }
	
	
 /**
  *写一下 二叉树的 版本
  *多叉树的 改成dp 超时
  * 怎 么   写 二叉树的 版本！
  */
	
	public int beautifulPartitionsByArignote(String s, int k, int minLength) {
		int[][] dp = new int[k + 1][s.length() + 1];
		dp[0][0] = 1;
		for (int i = 1; i <= k; i++) {
			int count = 0;
			for (int j = minLength - 1; j < s.length(); j++) {
//				count = (count + ((j < minLength || "2357".indexOf(s.charAt(j - minLength)) < 0)
//						&& "2357".indexOf(s.charAt(j - minLength + 1)) >= 0 ? dp[i - 1][j - minLength + 1] : 0))
//						% 1000000007;	
				count += ((j < minLength || "2357".indexOf(s.charAt(j - minLength)) < 0)
						&& 
						"2357".indexOf(s.charAt(j - minLength + 1)) >= 0 
						?
								dp[i - 1][j - minLength + 1] : 0);
				
				dp[i][j + 1] = "2357".indexOf(s.charAt(j)) < 0 ? count : 0;
			}
		}
		return dp[k][s.length()];
	}
	
	
}
